// DArray.h

#pragma once
#ifndef DARRAY_H_INCLUDED
#define DARRAY_H_INCLUDED

#include <new.h>

#pragma warning(push)
#pragma warning(disable:4127) // conditional expression is constant
#pragma warning(disable:4345) // POD initialization

template <typename Obj,bool bConstructor=true>
class DArray
{
public:
	DArray() : m_pxE(NULL), m_iCount(0) {};
	~DArray() {SetSize(0);if(m_pxE){free(m_pxE);};};

	bool ValidIndex(int p_iIdx) const {return (p_iIdx>=0)&&(p_iIdx<m_iCount);};

	void SetSize(int p_iNewSize)
	{
		if(p_iNewSize<0){p_iNewSize=0;};
		if (m_iCount<p_iNewSize)				// Grow ?
		{
			ReAllocMemory(p_iNewSize);
			if(bConstructor)
			{
				Construct(m_iCount,p_iNewSize-m_iCount);
			};
			m_iCount=p_iNewSize;
		}
		else
		if (m_iCount>p_iNewSize)				// Shrink ?
		{
			if(bConstructor)
			{
				Destruct(p_iNewSize,m_iCount-p_iNewSize);
			};
			ReAllocMemory(p_iNewSize);
			m_iCount=p_iNewSize;
		};
	};

	void Clear()
	{
		SetSize(0);
	};

	int Grow(int p_iAmount=1)
	{
		SetSize(GetSize()+p_iAmount);
		return GetSize();
	};

	int Shrink(int p_iAmount=1)
	{
		SetSize(GetSize()-p_iAmount);
		return GetSize();
	};

	void Delete(int p_iIndex,int p_iDelCount=1)
	{
		if(m_iCount == 0) {return;};
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		Destruct(p_iIndex,p_iDelCount);
		if(p_iIndex+p_iDelCount<m_iCount)
		{
			MoveElements(p_iIndex,p_iIndex+p_iDelCount,m_iCount-p_iIndex-p_iDelCount);
		};
		ReAllocMemory(m_iCount-p_iDelCount);
		m_iCount-=p_iDelCount;
	};

	void DeleteUS(int p_iIndex)
	{
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		Destruct(p_iIndex,1);
		MoveElements(p_iIndex,m_iCount-1,1);
		ReAllocMemory(m_iCount-1);
		--m_iCount;
	};

	int New()
	{
		SetSize(m_iCount+1);
		return m_iCount-1;
	};

	Obj& NewRef()
	{
		SetSize(m_iCount+1);
		return m_pxE[m_iCount-1];
	};

	int Add(const Obj& p_xA)
	{
		SetSize(m_iCount+1);
		m_pxE[m_iCount-1]=p_xA;
		return m_iCount-1;
	};

	int Insert(int p_iIndex)
	{
		assert((p_iIndex>=0)&&(p_iIndex<=m_iCount));
		ReAllocMemory(m_iCount+1);
		MoveElements(p_iIndex+1,p_iIndex,m_iCount-p_iIndex);
		++m_iCount;
		Construct(p_iIndex,1);
		return p_iIndex;
	};

	int Insert(int p_iIndex,int p_iCount)
	{
		assert((p_iIndex>=0)&&(p_iIndex<=1+m_iCount-p_iCount));
		ReAllocMemory(m_iCount+p_iCount);
		MoveElements(p_iIndex+p_iCount,p_iIndex,m_iCount-p_iIndex);
		m_iCount+=p_iCount;
		Construct(p_iIndex,p_iCount);
		return p_iIndex;
	};

	template<class ObjFind>
	int Find(const ObjFind& p_xA) const
	{
		int i,iC=GetSize();
		for(i=0;i<iC;i++)
		{
			if(m_pxE[i]==p_xA){return i;};
		};
		return -1;
	};

	size_t SizeOf() const
	{
		return m_iCount*sizeof(Obj);
	};

	Obj* Raw() const
	{
		return m_pxE;
	};

	DArray<Obj,bConstructor>* GetPtr()
	{
		return this;
	};

	int GetSize() const {return m_iCount;};

	const Obj& GetAtConst(int p_iIndex) const
	{
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		return m_pxE[p_iIndex];
	};

	Obj& GetAt(int p_iIndex)
	{
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		return m_pxE[p_iIndex];
	};

	Obj& operator[](int p_iIndex)
	{
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		return m_pxE[p_iIndex];
	};

	const Obj& operator[](int p_iIndex) const
	{
		assert((p_iIndex>=0)&&(p_iIndex<m_iCount));
		return m_pxE[p_iIndex];
	};

	Obj& Last()
	{
		assert(m_iCount>0);
		return m_pxE[m_iCount-1];
	};

	const Obj& LastConst() const
	{
		assert(m_iCount>0);
		return m_pxE[m_iCount-1];
	};

	int operator=(int p_iNewCount)
	{
		SetSize(p_iNewCount);
		return m_iCount;
	};

	int operator--(int)
	{
		SetSize(m_iCount-1);
		return m_iCount;
	};

	int operator--()
	{
		int iC=m_iCount;
		SetSize(m_iCount-1);
		return m_iCount;
	};

	int operator-=(int p_iAmount)
	{
		SetSize(m_iCount-p_iAmount);
		return m_iCount;
	};

	int operator++(int)
	{
		SetSize(m_iCount+1);
		return m_iCount;
	};

	int operator++()
	{
		int iC=m_iCount;
		SetSize(m_iCount+1);
		return m_iCount;
	};

	int operator+=(int p_iAmount)
	{
		SetSize(m_iCount+p_iAmount);
		return m_iCount;
	};

	bool Equal(const DArray<Obj,bConstructor> &p_axCompare) const
	{
		if(GetSize()!=p_axCompare.GetSize()){return false;};
		for(int i=0;i<GetSize();i++)
		{
			if(!(m_pxE[i]==p_axCompare.m_pxE[i]))
			{
				return false;
			};
		};
		return true;
	};

	bool operator==(const DArray<Obj,bConstructor> &p_axCompare) const
	{
		return Equal(p_axCompare);
	};

	DArray(const DArray<Obj,bConstructor> &p_axOrg)
	{
		m_pxE=NULL;m_iCount=0;
		int iSize=((0xf+p_axOrg.m_iCount)&~0xf);
		ReAllocMemory(iSize);

		if(bConstructor)
		{
			for (int i=0;i<p_axOrg.m_iCount;++i)
			{
				new (&m_pxE[i])Obj(p_axOrg.m_pxE[i]);
			};
		}
		else
		{
			memcpy(m_pxE,p_axOrg.m_pxE,sizeof(Obj)*p_axOrg.m_iCount);
		};
		m_iCount=p_axOrg.m_iCount;
	};
	
	// assignment operator
	DArray<Obj,bConstructor>& operator=(const DArray<Obj,bConstructor> &p_axOrg)
	{
		if (this == &p_axOrg) {return *this;};
		SetSize(p_axOrg.m_iCount);
		if (bConstructor)
		{
			for (int i=0;i<p_axOrg.m_iCount;++i)
			{
				m_pxE[i]=p_axOrg.m_pxE[i];
			};
		}
		else
		{
			memcpy(m_pxE,p_axOrg.m_pxE,sizeof(Obj)*p_axOrg.m_iCount);
		};
		return *this;
	};

	// Copy
	template<class ObjOther,bool bConstructorOther>
	void Copy(DArray<ObjOther,bConstructorOther> &p_xDest)
	{
		p_xDest.SetSize(m_iCount);
		ObjOther* pxDstE=p_xDest.Raw();
		if (bConstructor)
		{
			for (int i=0;i<m_iCount;++i)
			{
				pxDstE[i]=m_pxE[i];
			};
		}
		else
		{
			memcpy(pxDstE,m_pxE,sizeof(Obj)*m_iCount);
		};
	};

	Obj ArraySum() const
	{
		Obj xSum=0;
		int i,iC=GetSize();
		for(i=0;i<iC;i++)
		{
			xSum+=GetAtConst(i);
		};
		return xSum;
	};

	void Swap(DArray<Obj,bConstructor> &p_axA)
	{
		::Swap(m_iCount,p_axA.m_iCount);
		::Swap(m_pxE,p_axA.m_pxE);
	};

	void Join(DArray<Obj,bConstructor> &p_axA)
	{
		int iS=m_iCount;
		SetSize(m_iCount+p_axA.m_iCount);
		for(int i=0;i<p_axA.m_iCount;i++)
		{
			m_pxE[iS+i]=p_axA.m_pxE[i];
		};
	};

	void BSort() //bubble sort, slow but stable
	{
		bool bSwap;
		do
		{
			bSwap=false;
			for(int i=0;i<GetSize()-1;i++)
			{
				if(m_pxE[i]>m_pxE[i+1])
				{
					Swap(m_pxE[i],m_pxE[i+1]);
					bSwap=true;
				};
			};
		} while(bSwap);
	};

	void QSort()
	{
		QSortSub(0,m_iCount-1);
	};

	void QSortSub(int p_iLoP,int p_iHiP)
	{
		if (p_iLoP>=p_iHiP) {return;};
		int iLo=p_iLoP,iHi=p_iHiP;
		if (iLo==iHi-1) {
			Obj xSwp;
			if (m_pxE[(iLo)]>m_pxE[(iHi)]) {xSwp=m_pxE[(iLo)];m_pxE[(iLo)]=m_pxE[(iHi)];m_pxE[(iHi)]=xSwp;};
			return;
		};
		Obj xPivot=m_pxE[((iLo+iHi)/2)];
		m_pxE[((iLo+iHi)/2)]=m_pxE[(iHi)];
		m_pxE[(iHi)]=xPivot;
		while (iLo<iHi) {
			while ((!(m_pxE[(iLo)]>xPivot)) && (iLo<iHi)) {++iLo;};
			while ((!(xPivot>m_pxE[(iHi)])) && (iLo<iHi)) {--iHi;};
			if (iLo<iHi) {
				Obj xSwp;
				xSwp=m_pxE[(iLo)];m_pxE[(iLo)]=m_pxE[(iHi)];m_pxE[(iHi)]=xSwp;};
		};
		m_pxE[(p_iHiP)]=m_pxE[(iHi)];m_pxE[(iHi)]=xPivot;
		QSortSub(p_iLoP,iLo-1);QSortSub(iHi+1,p_iHiP);
	};

	void QSort(void* p_pxUserData)
	{
		QSortSub(0,m_iCount-1,p_pxUserData);
	};

	void QSortSub(int p_iLoP,int p_iHiP,void* p_pxUserData)
	{
		if (p_iLoP>=p_iHiP) {return;};
		int iLo=p_iLoP,iHi=p_iHiP;
		Obj xSwp;
		if (iLo==iHi-1) {
			if (m_pxE[(iLo)].Greater(m_pxE[(iHi)],p_pxUserData)) {xSwp=m_pxE[(iLo)];m_pxE[(iLo)]=m_pxE[(iHi)];m_pxE[(iHi)]=xSwp;};
			return;
		};
		Obj xPivot=m_pxE[((iLo+iHi)/2)];
		m_pxE[((iLo+iHi)/2)]=m_pxE[(iHi)];
		m_pxE[(iHi)]=xPivot;
		while (iLo<iHi) {
			while ((!(m_pxE[(iLo)].Greater(xPivot,p_pxUserData))) && (iLo<iHi)) {++iLo;};
			while ((!(xPivot.Greater(m_pxE[(iHi)],p_pxUserData))) && (iLo<iHi)) {--iHi;};
			if (iLo<iHi) {xSwp=m_pxE[(iLo)];m_pxE[(iLo)]=m_pxE[(iHi)];m_pxE[(iHi)]=xSwp;};
		};
		m_pxE[(p_iHiP)]=m_pxE[(iHi)];m_pxE[(iHi)]=xPivot;
		QSortSub(p_iLoP,iLo-1,p_pxUserData);QSortSub(iHi+1,p_iHiP,p_pxUserData);
	};

protected:
	Obj*	m_pxE;
	int		m_iCount;

	void ValidateIndex(int p_iIndex) {p_iIndex;};

	void Construct(int p_iIndex,int m_iCount)
	{
		ValidateIndex(p_iIndex);
		ValidateIndex(p_iIndex+m_iCount-1);
		int i;
		for(i=p_iIndex;i<p_iIndex+m_iCount;i++)
		{
			new (&(m_pxE[i])) Obj();
		};
	};

	void Destruct(int p_iIndex,int m_iCount)
	{
		ValidateIndex(p_iIndex);
		ValidateIndex(p_iIndex+m_iCount-1);
		int i;
		for(i=p_iIndex;i<p_iIndex+m_iCount;i++)
		{
			m_pxE[i].~Obj();
		};
	};

	void ReAllocMemory(int p_iSize)
	{
		int iOld=m_iCount;
		DWORD dwOldSize=((0xf+(iOld))&~0xf);
		DWORD dwRNewSize=((0xf+(p_iSize))&~0xf);
		if (dwRNewSize!=dwOldSize)
		{
			if(dwRNewSize==0)
			{
				free(m_pxE);
				m_pxE=NULL;
			}
			else
			{
				m_pxE=(Obj*)realloc(m_pxE,dwRNewSize*sizeof(Obj));
			};
		};
	};

	void MoveElements(int p_iDstIndex,int p_iSrcIndex,int p_iCount)
	{
		if((p_iDstIndex!=p_iSrcIndex)&&(p_iCount>0))
		{
			memmove(&(m_pxE[(p_iDstIndex)]),&(m_pxE[(p_iSrcIndex)]),sizeof(Obj)*p_iCount);
		};
	};

};

#pragma warning(pop)

#endif // DARRAY_H_INCLUDED
